package NiuKe;

import java.util.HashSet;
import java.util.Scanner;

/**
 * 我们称一个长度为n的序列为正则序列，
 * 当且仅当该序列是一个由1~n组成的排列，
 * 即该序列由n个正整数组成，取值在[1,n]范围，
 * 且不存在重复的数，同时正则序列不要求排序
 * 有一天小团得到了一个长度为n的任意序列s，
 * 他需要在有限次操作内，将这个序列变成一个正则序列，
 * 每次操作他可以任选序列中的一个数字，并将该数字加一或者减一。
 * 请问他最少用多少次操作可以把这个序列变成正则序列？
 */
public class Regular {
    public static void main(String[] args) {
        for(int i = 153;i < 1000; i++){
            int hunders = i / 100;
            int tens = (i % 100) / 10;
            int ones = i % 100 % 10;
            int sum = (int)Math.pow(hunders, 3) + (int)Math.pow(tens, 3) + (int)Math.pow(ones, 3);
            if(sum == i){
                System.out.println(i);
            }
        }
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int[] array = new int[n];
//        for (int i = 0; i < n; i++) {
//            int m = scanner.nextInt();
//            array[i] = m;
//        }
//        System.out.println(solution(array, n));
    }

    public static int solution(int[] array, int n) {
        int sum = 0;
        merge(array, 0, array.length - 1, new int[array.length]);
        for (int i = 1; i <= n; i++) {
            sum += Math.abs(array[i-1]-i);
        }
        return sum;
    }

    public static void merge(int[] array, int left, int right, int[] temp) {
//        System.out.println(left+":"+right);
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;
        merge(array, left, mid, temp);
        merge(array, mid + 1, right, temp);

        for (int i = left; i <= right; i++) {
            temp[i] = array[i];
        }
        int n = left;
        int m = mid + 1;
        for (int i = left; i <= right; i++) {
            if (n == mid + 1) {
                array[i] = temp[m];
                m++;
            } else if (m == right + 1) {
                array[i] = temp[n];
                n++;
            } else if (temp[n] <= temp[m]) {
                array[i] = temp[n];
                n++;
            } else {
                array[i] = temp[m];
                m++;
            }
        }
    }
}
